package io.github.hadyang.leetcode.offer;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import org.junit.Test;

/** @author haoyang.shi */
public class Permutation {

  @Test
  public void test() {
    System.out.println(Permutation("abc"));
  }

  public ArrayList<String> Permutation(String str) {
    Set<String> res = new HashSet<>();

    if (str == null || str.length() == 0) {
      return new ArrayList<>();
    }

    Permutation(res, str.toCharArray(), 0);

    ArrayList<String> list = new ArrayList<>(res);

    list.sort(String::compareTo);
    return list;
  }

  private void Permutation(Set<String> res, char[] chars, int start) {
    if (start == chars.length) {
      res.add(new String(chars));
      return;
    }

    for (int i = start; i < chars.length; i++) {
      swap(chars, start, i);

      Permutation(res, chars, start + 1);

      swap(chars, start, i);
    }
  }

  private void swap(char[] chars, int i, int j) {
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
  }
}
